Yellow page telephone directories, so called because of the color of the paper on which they are printed, include advertisements and listings for commercial establishments organized by categories. The advertisements and listings are laid out according to certain rules and guidelines which relate to the pricing structure for entries in the yellow pages. Larger advertisements, which are more expensive, are placed before smaller advertisements within a category or section. Advertisements must be on the pages for the categories to which the advertisement belongs. The listings include the entities in alphabetical order and small "in-line" advertisements, which are in the appropriate alphabetical position. Typically, yellow pages are laid out in four columns. The size of advertisements are defined by the number of columns of width and a height. Since people typically begin looking for a commercial establishment at the beginning of a category, the advertisements are placed as close to the beginning as possible. Pagination and layout of the advertisements within these rules and guidelines can be extremely difficult. Typically the process is done by hand by groups of people who determine reasonable layouts. No attempt is made to optimize the layout; in order to meet the requirements, considerable space is wasted on each page. It is estimated that ten to fifteen percent of the total available space in a yellow page directory is wasted. This corresponds to an annual waste of 2,000 to 3,000 tons of paper just for the yellow page directories for the New York and New England areas of the United States.
Document formatting problems arise in the publication of different types of material. Research in the area of automated formatting of documents with computers has focused on formatting text. Pagination and page layout problems have received less attention. Two different approaches have been used in automatically paginating and laying out pages which could be applied to yellow pages. In a rule based approach, described in H. G. Chew, M. Liang, P. Koh, D. Ong, and J. H. Tan, "ALEXIS: An intelligent layout tool for publishing," in Proceedings of the Sixth Annual Conference on Innovative Applications of Artificial Intelligence, (August 1994) pp. 41-47, and J. P. Rosenking, H. J. Marmorstein, E. M. Baron-Vartian, and R. W. Soccio, "A Generic System for Directory Pagination," in Proceedings of the IEEE/ACM International Conference on Developing and Managing Expert System Programs, (April 1991) pp. 166-169 include a set of if-then rules which define specific decisions to be made in meeting the guidelines with certain advertisement and text configurations. The rule based system has been useful in assisting people who actually layout the pages. Its use has resulted in modest savings, on the order of 1-2% of pages. However, the number of possible configurations is quite large and a reasonably sized rule base cannot accommodate all configurations. Thus, it is unlikely that a set of rules can be accurately defined in order to optimize page layout.
A dynamic programming approach, discussed in M. F. Plass, "Optimal Pagination Techniques for Automatic Typesetting Systems," Stamford University (1981), could be applied to determining pagination and layout for yellow pages. However, use of the algorithms described in Plass to determine an automatic system for pagination and layout of yellow pages which is sufficient would be very challenging, and may be impossible.
The prior art systems fail to provide a method for automatically paginating and laying out yellow pages which can result in a significant reduction of wasted space. Therefore, it is an object of the present invention to provide a system which can optimize yellow page layout.